//在排序数组中查找元素的第一个和最后一个位置   力扣34
//二分查找
//总结：当存在多个target时，四种方式的二分查找结束时，指针情况分别为
//      左闭右开：对于左边界的查找：两指针位于=第一个target的位置
//                对于右边界的查找：两指针位于>最后一个target的位置
//      左开右闭：对于左边界的查找：两指针位于<第一个target的位置
//                对于右边界的查找：两指针位于=最后一个target的位置
//      左闭右闭：对于左边界的查找：左指针位于>第一个target的位置,右指针位于<第一个target的位置
//                对于右边界的查找：左指针位于>最后一个target的位置,右指针位于<第一个target的位置
//      左开右闭：对于左边界的查找：左指针位于<第一个target的位置,右指针位于>第一个target的位置
//                对于右边界的查找：左指针位于<最后一个target的位置,右指针位于>第一个target的位置
//另外：为了区分target存在但在最左边或最右边 和 target小于最小值或大于最大值 的情况，
//      使用了leftboard 和 rightboard，当出现nums[mid] = target的情况时这两个指针才会发生改变，
//      否则就一直为初始值，表示没有查找到target，根据选择的开闭情况以及题意，合理选择初值
//左闭右开
class Solution {
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		//左边界
		int leftboard = -1;//用来标识是否找到了target，若找不到，则leftboard不变，刚好为-1
		int left = 0;
		int right = nums.size();
		while(left < right)
		{
			int mid = left + (right - left) / 2;
			if(nums[mid] < target) left = mid + 1;
			else if(nums[mid] > target) right = mid;
			else 
			{
				right = mid;
				leftboard = right;
			}
		}
		//右边界
		int rightboar = 0;//用来标识是否找到了target，若找不到，则rightboard不变，减1后刚好为-1
		left = 0;
		right = nums.size();
		while(left < right)
		{
			int mid = left + (right - left) / 2;
			if(nums[mid] < target) left = mid + 1;
			else if(nums[mid] > target) right = mid;
			else
			{
				left = mid + 1;
				rightboar = left;
			}
		}
		return {leftboard,rightboar-1};
		
	}
};

//左开右闭
class Solution {
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		//左边界
		int leftboard = -2;
		int left = -1;
		int right = nums.size()-1;
		while(left < right)
		{
			int mid = left + (right - left) / 2 + 1;
			if(nums[mid] < target) left = mid;
			else if(nums[mid] > target) right = mid - 1;
			else 
			{
				right = mid - 1;  //与>时的情况保持一致
				leftboard = right;
			}
		}
		//右边界
		int rightboard = -1;
		left = -1;
		right = nums.size() - 1;
		while(left < right)
		{
			int mid = left + (right - left) / 2 + 1;
			if(nums[mid] < target) left = mid;
			else if(nums[mid] > target) right = mid - 1;
			else 
			{
				left = mid;//与<时情况保持一致
				rightboard = left;
			}
			
		}
		return {leftboard + 1, rightboard};
	}
};
//左闭右闭
class Solution {
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		//左边界
		int leftboard = -2;
		int left = 0;
		int right = nums.size()-1;
		while(left <= right)
		{
			int mid = left + (right - left) / 2;
			if(nums[mid] < target) left = mid + 1;
			else if(nums[mid] > target) right = mid - 1;
			else
			{
				right = mid - 1;
				leftboard = right;
			} 
		}
		//右边界
		int rightboard = 0;
		left = 0;
		right = nums.size()-1;
		while(left <= right)
		{
			int mid = left + (right - left) / 2;
			if(nums[mid] < target) left = mid + 1;
			else if(nums[mid] > target) right = mid - 1;
			else
			{
				left = mid + 1;
				rightboard = left;
			}
		}
		return {leftboard + 1,rightboard - 1};
	}
};
//左开右开
class Solution {
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		//左边界
		int leftboard = -1;
		int left = -1;
		int right = nums.size();
		while(left + 1 != right)
		{
			int mid = left + (right - left) / 2;
			if(nums[mid] < target) left = mid;
			else if(nums[mid] > target) right = mid;
			else
			{
				right = mid;
				leftboard = right;
			}
		}
		//右边界
		int rightboard = -1;
		left = -1;
		right = nums.size();
		while(left + 1 != right)
		{
			int mid = left + (right - left) / 2;
			if(nums[mid] <  target) left = mid;
			else if(nums[mid] > target) right = mid;
			else
			{
				left = mid;
				rightboard = left;
			}
		}
		return {leftboard,rightboard};
	}
};
